package com.xzz.treeBST;


/**
 * @author: hhz
 * @create: 2022-01-20 16:21
 **/
public class SortedListToBST {
    public static void main(String[] args) {
        ListNode head = new ListNode(-10,new ListNode(-3,new ListNode(0,new ListNode(5,new ListNode(9)))));
        TreeNode treeNode = sortedListToBST(head);
        System.out.println();
    }
    public static TreeNode sortedListToBST(ListNode head) {
        return build(head,null);
    }
    public static TreeNode build(ListNode left,ListNode right){
        if(left==right){
            return null;
        }
        ListNode mid = getMin( left, right);
        TreeNode node = new TreeNode(mid.val);
        node.left = build(left,mid);
        node.right = build(mid.next,right);
        return node;

    }

    private static ListNode getMin(ListNode left, ListNode right) {
        ListNode slow = left;
        ListNode fast = left;
        while (fast!=right && fast.next!=right){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
